from collections import OrderedDict, deque
from threading import Lock
import time


class LimitDict(OrderedDict):
    def __init__(self, max_len):
        super().__init__()
        self.max_len = max_len

    def __setitem__(self, key, value):
        super().__setitem__(key, value)
        while len(self) > self.max_len:
            self.popitem(False)


class RecentDict:
    def __init__(self, keep):
        self._ordered_dict = OrderedDict()
        self.keep = keep

    def __contains__(self, item):
        self._cut()
        return item in self._ordered_dict

    def __getitem__(self, item):
        self._cut()
        return self._ordered_dict[item][1]

    def __setitem__(self, key, value):
        now = time.time()
        self._ordered_dict[key] = (now, value)

    def __delitem__(self, key):
        del self._ordered_dict[key]

    def _cut(self):
        cut_before = time.time() - self.keep
        to_cut = 0
        dic = self._ordered_dict
        for key, value in dic.items():
            if value[0] < cut_before:
                to_cut += 1
            else:
                break

        for i in range(to_cut):
            dic.popitem(False)


class ActiveDict:
    def __init__(self, max_len):
        self._ordered_dic = OrderedDict()
        self._lock = Lock()
        self._max_len = max_len

    def __repr__(self):
        return self._ordered_dic.__repr__()

    def __setitem__(self, key, value):
        dic = self._ordered_dic
        with self._lock:
            if key in dic:
                del dic[key]
            dic[key] = value

            while len(dic) > self._max_len:
                dic.popitem(False)

    def __getitem__(self, key):
        dic = self._ordered_dic
        with self._lock:
            value = dic[key]
            del dic[key]
            dic[key] = value

    def get(self, key, default=None):
        dic = self._ordered_dic
        with self._lock:
            if key not in dic:
                return default
            value = dic[key]
            del dic[key]
            dic[key] = value


class LimitRecentDict:
    def __init__(self, limit, recent):
        self._ordered_dict = OrderedDict()
        self.limit = limit
        self.recent = recent

    def __repr__(self):
        self._cut()
        return self._ordered_dict.__repr__()

    def __len__(self):
        self._cut()
        return len(self._ordered_dict)

    def __contains__(self, item):
        self._cut()
        return item in self._ordered_dict

    def __getitem__(self, item):
        self._cut()
        return self._ordered_dict[item][1]

    def __setitem__(self, key, value):
        now = time.time()
        self._ordered_dict[key] = (now, value)

    def __delitem__(self, key):
        del self._ordered_dict[key]

    def _cut(self):
        dic = self._ordered_dict
        limit = self.limit
        while len(dic) > limit:
            dic.popitem(False)

        cut_before = time.time() - self.recent
        to_cut = 0
        for key, value in dic.items():
            if value[0] < cut_before:
                to_cut += 1
            else:
                break

        for i in range(to_cut):
            dic.popitem(False)


class MedianQueue:
    def __init__(self, n, single=False):
        self._n = n
        self._i = int(n // 2)
        self._queue = deque(maxlen=n)

        if single is True:
            self.median = self._median_1
        elif n % 2 == 0:
            self.median = self._median_2
        else:
            self.median = self._median_1

    def push(self, value):
        self._queue.append(value)

    def _median_1(self):
        if len(self._queue) < self._n:
            return None

        sort = sorted(self._queue)
        return sort[self._i]

    def _median_2(self):
        if len(self._queue) < self._n:
            return None

        i = self._i
        sort = sorted(self._queue)
        return (sort[i-1] + sort[i]) / 2


if __name__ == '__main__':
    med = MedianQueue(3)
    med.push(1)
    print(med.median())
    med.push(2)
    print(med.median())
    med.push(3)
    print(med.median())
    med.push(4)
    print(med.median())
















